//
//  Dynamic Huffman Encoder/Decoder
//
//  implemented by Gangta
//
//-----------------------------------------------------------
//
//  Version History
//
//  version 0.1  - first release
//  version 0.1a - fixed a bug where the bit remainder in
//                 the EncodeBuffer() function didn't reset
//                 to 32 if encoding is restarted before
//                 program exit
//  version 0.1b - fixed right shift
//               - fixed some utility functions
//
//  version 0.1c - fixed PrintResult()
//               - fixed a fatal bug in CorrectDH_T) 15% slower
//               - optimized compression/decompression 95% faster
//               - overall 80% faster :)
//
//  version 0.2  - optimized even more, now O(lg 2) :)
//
//-----------------------------------------------------------
//
//  Memory usage:
//
//     128 KB for both encoding/decoding
//
//     I tested buffer size 16K, 32K, 64K, 128K, etc
//     The performance started to drop after 512K,
//     so I chose 128K.
//
//  Comments:
//
//     I tried to optimize the speed as best I can in my
//     knowledge.
//
//     It has buffer overflow protection for encoding and
//     decoding.
//
//     It has a frequency reset function which prevents
//     frequency overflow.
//
//     It can compress text files as well as any type of
//     binary files.  The compression is not as good as
//     zlib, or bzlibb2, but it supports "on the fly"
//     encoding/decoding, and I believe it is faster than
//     bzlibb2.
//
//
///////////////////////////////////////////////////////////////

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "dynhuff.h"

#ifndef UINT32
#define   UINT32 unsigned int
#endif

//#
//#             Data sets for Dynamic Huffman Encoding/Decoding
//#
//##############################################################################

// data sets for dynamic huffman
struct DHTNode
{
    unsigned int   freq;
    unsigned char  value;
    struct DHTNode *left;
    struct DHTNode *right;
    struct DHTNode *parent;
    int            l_index; // where this node is in the list
};
static struct DHTNode DHTroot = {0, 0, NULL, NULL, NULL, 0};
static struct DHTNode *null_node_ptr = &DHTroot;          // where to add a new data
static struct DHTNode *look_up_table[257] = {NULL,};      // check if it's a new data
static struct DHTNode *node_list[MAX_LIST_LEN] = {NULL,}; // reverse level traverse
static int list_idx = MAX_LIST_LEN - 1;

// data sets for compressed buffer and compressed file I/O
static FILE   *cFile = NULL;
static UINT32 *c_buffer = NULL;
static int     c_buffer_idx = 0;
static int     c_buffer_size = 0;
int end_of_buffer = 0;
static int code_length = 0;

// data sets for decompressed buffer and decompressed file I/O
static FILE   *dFile = NULL;
static UINT32  d_buffer[MAX_BUFFER_LEN] = {0,};
static int     d_buffer_idx  = 0;

// file embedding
static int bEmbed = 0;
static int embed_offset = 0;

// flags used to determine when to stop decoding
static unsigned int code_count = 0;
static int    code_reset_count = 0;

// for saving compression result
static unsigned int nCompressedFileSize; // flag
static unsigned int nCodeCount;          // flag
static int          nCodeResetCount;     // flag
static int          nBufferIdx;
static int          nBufferResetCount;   // flag

// for decompressing
static struct DecodeStatus
{
    UINT32 code_slice;  // slice of a buffer element
    int bit_counter;    // if 32, get a new slice
    unsigned int nCode; // how many codes has been decoded so far
    int nCodeReset;     // how many times the data counter has been reset
} dcs;

// function prototypes
static void AllocBufferC(int size);
static void GrowBufferC();
static void ResetBufferD();
static void ReloadBufferD();
static void SaveResult();
#ifdef _DEBUG
static void CheckList();
#endif

//#
//#             Functions for Dynamic Huffman Encoding/Decoding
//#
//##############################################################################

// initialize a node in the dynamic huffman tree
static void SetNode (struct DHTNode *node_ptr, unsigned int freq, unsigned char value, struct DHTNode *left, struct DHTNode *right, struct DHTNode *parent)
{
    node_ptr->freq   = freq;   // count # of occurances
    node_ptr->value  = value;  // corresponding key in the mInputSet
    node_ptr->left   = left;   // left subtree
    node_ptr->right  = right;  // right subtree
    node_ptr->parent = parent; // parent node
}

// the list is a reverse level traversal of the dynamic huffman tree
static void BuildNodeList (struct DHTNode *node_ptr)
{
    if(list_idx == MAX_LIST_LEN - 1)
    {
        node_list[MAX_LIST_LEN - 1] = NULL;
    }
    node_list[--list_idx] = node_ptr->parent;
    node_ptr->parent->l_index = list_idx;
    node_list[--list_idx] = node_ptr;
    node_ptr->l_index = list_idx;
}

// swap the two nodes in the dynamic huffman tree
static void SwapNodes (struct DHTNode *node1, struct DHTNode *node2)
{
    unsigned int freq_diff;
    struct DHTNode temp_node;
    struct DHTNode *node_ptr = node1; // node1 always has higher freq

    // backup node1 before swapping
    memcpy(&temp_node, node1, sizeof(struct DHTNode));

    // swap each node's parent's left or right depending on
    // whether each noce is a left child or a right child
    if(node2->parent->left == node2)
        node2->parent->left = node1;
    else
        node2->parent->right = node1;
    if(temp_node.parent->left == node1)
        node1->parent->left = node2;
    else
        node1->parent->right = node2;

    // swap each node's parent
    node1->parent = node2->parent;
    node2->parent = temp_node.parent;

    // swap each node's l_index
    node1->l_index = node2->l_index;
    node2->l_index = temp_node.l_index;

    // correct frequencies
    freq_diff = node1->freq - node2->freq;
    node_ptr = node1;
    while(node_ptr->parent)
    {
        node_ptr = node_ptr->parent;
        node_ptr->freq += freq_diff;
    }
    node_ptr = node2;
    while(node_ptr->parent)
    {
        node_ptr = node_ptr->parent;
        node_ptr->freq -= freq_diff;
    }
}

// correct the dynamic huffman tree if necessary
static void CorrectDHT(int curr_idx)
{
    struct DHTNode *temp;
    int swap_idx;

    // search for nodes that are not in order
    while(node_list[curr_idx + 1])
    {
        // if found something out of order
        if(node_list[curr_idx]->freq > node_list[curr_idx + 1]->freq)
        {
            // search for the node to swap with, then swap them
            swap_idx = curr_idx + 1;
            while(node_list[swap_idx + 1])
            {
                // found node to swap it with, so swap them,
                if(node_list[swap_idx]->freq < node_list[swap_idx + 1]->freq)
                {
                    // extra check for null node exception
                    if(node_list[list_idx]->parent == node_list[curr_idx])
                    {
                        SwapNodes(node_list[list_idx], node_list[swap_idx]);
                        temp = node_list[list_idx];
                        node_list[list_idx] = node_list[swap_idx];
                        node_list[swap_idx] = temp;
                    }
                    else
                    {
                        SwapNodes(node_list[curr_idx], node_list[swap_idx]);
                        temp = node_list[curr_idx];
                        node_list[curr_idx] = node_list[swap_idx];
                        node_list[swap_idx] = temp;
                    }

                    if(node_list[swap_idx]->parent)
                        CorrectDHT(node_list[swap_idx]->parent->l_index);

                    return;
                }
                ++swap_idx;
            }
        }
        if(!(node_list[curr_idx]->parent))
            return;
        curr_idx = node_list[curr_idx]->parent->l_index;
    }
}

// prevent node frequency from overflowing
static void ResetFrequency()
{
    int idx = list_idx; // start with the bottom left node

    node_list[idx++]->freq = 1;
    node_list[idx++]->freq = 1;

    while(node_list[idx])
    {
        // if it's a leaf, set it to the minimum possible frequency
        if(!node_list[idx]->right)
            node_list[idx]->freq = node_list[idx - 1]->freq;
        // if it's a joint node, set the frequency to left + right
        else if(node_list[idx]->left)
            node_list[idx]->freq = node_list[idx]->left->freq + node_list[idx]->right->freq;
        ++idx;
    }
}

// build the dynamic huffman tree
static void BuildDHT (unsigned char data)
{
    struct DHTNode *node_ptr = look_up_table[data];
    struct DHTNode *update_node_ptr = NULL;

    // if tree is empty, initialize the tree
    if(!DHTroot.freq)
    {
        null_node_ptr->right = (struct DHTNode *)malloc(sizeof(struct DHTNode));
        SetNode(&DHTroot, 1, 0, NULL, DHTroot.right, NULL);
        SetNode(DHTroot.right, 1, data, NULL, NULL, &DHTroot);

        look_up_table[data] = DHTroot.right;
        BuildNodeList(look_up_table[data]);
    }
    // if the data already exists in the tree,
    // just increment the node counter
    else if(look_up_table[data])
    {
        // reset frequencies before they overflow
        if(DHTroot.freq + 1 > MAX_FREQ) ResetFrequency();

        // increment node frequency
        node_ptr->freq += 1;

        // reduce level of reverse level traversing (optimization)
        if(node_ptr->parent != null_node_ptr && node_ptr->freq > node_list[(node_ptr->l_index) + 1]->freq)
            update_node_ptr = node_ptr;

        // increment frequencies for all its ancestors
        node_ptr = node_ptr->parent;
        while (node_ptr)
        {
            node_ptr->freq += 1;

            // reduce level of reverse level traversing (optimization)
            if(!update_node_ptr && node_ptr->parent && node_ptr->freq > node_list[(node_ptr->l_index) + 1]->freq)
                update_node_ptr = node_ptr;

            node_ptr = node_ptr->parent;
        }

        // correct the dynamic huffman tree if neccessary
        if(update_node_ptr) CorrectDHT(update_node_ptr->l_index);
    }
    // if it's a new data, insert it into a new node
    else
    {
        // reset frequencies before they overflow
        if(DHTroot.freq + 1 > MAX_FREQ) ResetFrequency();

        null_node_ptr->left = (struct DHTNode *)malloc(sizeof(struct DHTNode));
        SetNode(null_node_ptr->left, 1, 0, NULL, NULL, null_node_ptr);
        null_node_ptr = null_node_ptr->left;

        null_node_ptr->right = (struct DHTNode *)malloc(sizeof(struct DHTNode));
        SetNode(null_node_ptr->right, 1, data, NULL, NULL, null_node_ptr);

        look_up_table[data] = null_node_ptr->right;
        BuildNodeList(look_up_table[data]);

        // increment frequencies of all its ancestors
        node_ptr = null_node_ptr->parent;
        while (node_ptr)
        {
            node_ptr->freq += 1;

            // reduce level of reverse level traversing (optimization)
            if(!update_node_ptr && node_ptr->parent && node_ptr->freq > node_list[(node_ptr->l_index) + 1]->freq)
                update_node_ptr = node_ptr;

            node_ptr = node_ptr->parent;
        }

        // correct the dynamic huffman tree if necessary
        if(update_node_ptr) CorrectDHT(list_idx);
    }
}

static void RemoveLookup(struct DHTNode *node_ptr)
{
    // to aid in cleanup / avoid calling free on a pointer twice in "reset lookup table"
    for(int i = 0; i < 257; i++)
    {
        if (look_up_table[i] == node_ptr)
            look_up_table[i] = NULL;
    }
}

// clean-ups
static void DestroyDHT()
{
    int i;

    // free all nodes in the dynamic huffman tree
    // and reset the node list
    list_idx = 0;
    while(list_idx < MAX_LIST_LEN - 3)
    {
        if (node_list[list_idx])
        {
            RemoveLookup(node_list[list_idx]);
            free(node_list[list_idx]);
            node_list[list_idx] = NULL;
        }
        ++list_idx;
    }
    node_list[MAX_LIST_LEN - 2] = NULL;
    node_list[MAX_LIST_LEN - 1] = NULL;
    list_idx = MAX_LIST_LEN - 1;

    // reset lookup table
    for(i = 0; i < 257; i++)
    {
        if (look_up_table[i]) free(look_up_table[i]);
        look_up_table[i] = NULL;
    }

    // reset the root node and null node pointer
    SetNode (&DHTroot, 0, 0, NULL, NULL, NULL);
    null_node_ptr = &DHTroot;
    end_of_buffer = 0;
}

// return the reverse path for the data existing in the tree
static UINT32 ReverseDataPath(struct DHTNode *node_ptr)
{
    UINT32 path_reverse = 0;
    code_length = 0;

    while(node_ptr->parent)
    {
        path_reverse <<= 1;

        if(node_ptr->parent->left == node_ptr)
            path_reverse &= 0xFFFFFFFE;  // fill the bit with 0
        else
            path_reverse |= 1;           // fill the bit with 1

        node_ptr = node_ptr->parent;
        ++code_length;
    }

    return path_reverse;
}

// generates and return a reverse code
static UINT32 GenerateReverseCode(unsigned char data)
{
    UINT32 path_reverse = 0;
    UINT32 code_reverse = 0;
    int i;

    // this data exists in the tree, so code is just
    // return the reverse path of the data
    if(look_up_table[data]) return ReverseDataPath(look_up_table[data]);

    // reverse the code
    for(i = 0; i < 8; i++)
    {
        code_reverse <<= 1;      // shift path_reverse 1 bit to the left
        code_reverse |= data & 1; // get the first bit
        data >>= 1;              // shift data 1 bit to the right
    }

    // tree is empty, the reverse code is
    // just the original data reversed.
    if(!DHTroot.freq)
    {
        code_length = 8;
        return code_reverse;   // return the reversed code
    }

    // it's a new data. get the reverse path for the null
    // node and append it after the reverse code
    path_reverse = ReverseDataPath(node_list[list_idx]->parent);
    ++code_length;    // for the null node path (0)
    code_reverse <<= code_length;
    code_length += 8;
    return code_reverse | path_reverse;
}

//#
//#             Functions for Buffer Handling
//#
//##############################################################################

// takes a decompressed file and compresses the whole thing into another file
int Compress(char *d_file_name, char *c_file_name)
{
    int i, nRet;
    UINT32 code_slice;
    unsigned char data;
    int byte_count;
    int bytes_remain;

    nRet = OpenDecompressedFile(d_file_name, "rb");
    if(nRet) return nRet;

    nRet = OpenCompressedFile(c_file_name, "wb");
    if(nRet) return nRet;

    // get file size (# of bytes)
    fseek(dFile, 0, SEEK_END);
    byte_count = ftell(dFile);
    fseek(dFile, 0, SEEK_SET);

    // if buffer is smaller than the file, load max allowed bytes
    // into the buffer, otherwise, load everything into the buffer
    if(byte_count * 4 > MAX_BUFFER_LEN)
        fread(d_buffer, 4, MAX_BUFFER_LEN, dFile);
    else
        fread(d_buffer, 1, byte_count, dFile);

    d_buffer_idx = 0;
    code_slice = d_buffer[0];
    bytes_remain = byte_count % 4;
    byte_count /= 4;

    for(i = 0; i < byte_count; i++)
    {
        data = (unsigned char)(code_slice >> 24);
        EncodeBuffer(data);
        data = (unsigned char)((code_slice >> 16) & 0xFF);
        EncodeBuffer(data);
        data = (unsigned char)((code_slice >> 8) & 0xFF);
        EncodeBuffer(data);
        data = (unsigned char)(code_slice & 0xFF);
        EncodeBuffer(data);

        // prevent buffer overflow
        if(++d_buffer_idx == MAX_BUFFER_LEN)
        {
            ReloadBufferD();
        }
        code_slice = d_buffer[d_buffer_idx];
    }
    if(bytes_remain)
    {
        code_slice <<= 32 - (bytes_remain * 8);
        for(i = 0; i < bytes_remain; i++)
        {
            data = (unsigned char)(code_slice >> 24);
            EncodeBuffer(data);
            code_slice <<= 8;
        }
    }
    CloseDecompressedFile();
    WriteCompressedFile();
    return nRet;
}

// takes a compressed file and decompresses the whole thing into another file
int Decompress(char *c_file_name, char *d_file_name)
{
    int remainder      = 32;
    UINT32 code_slice  = 0;
    int bytes_remain   = 0;
    int nRet;

    nRet = OpenCompressedFile(c_file_name, "rb");
    if(nRet) return nRet;

    nRet = OpenDecompressedFile(d_file_name, "wb");
    if(nRet) return nRet;

    LoadCompressedFile();

    d_buffer[0] = 0;
    d_buffer_idx = 0;

    while(!end_of_buffer)
    {
        code_slice = (UINT32)DecodeBuffer();
        remainder -= 8;
        code_slice <<= remainder;
        d_buffer[d_buffer_idx] |= code_slice;

        if(!remainder)
        {
            if(++d_buffer_idx == MAX_BUFFER_LEN) ResetBufferD();
            d_buffer[d_buffer_idx] = 0;
            remainder = 32;
        }
    }
    bytes_remain = (32 - remainder) / 8;

    CloseCompressedFile();
    WriteDecompressedFile(bytes_remain);
    return nRet;
}

// take a data and encode it into c_buffer
void EncodeBuffer(unsigned char data)
{
    UINT32 code      = 0;     // code that is ready to put into the buffer
    UINT32 code_temp = 0;     // used to break the code into two parts
    UINT32 code_reverse;
    int i;

    // at the beginning, reset everything
    // also fill 0s for the headers (coude_count, code_reset_count, buffer_reset_count)
    if(!DHTroot.freq)
    {
        dcs.bit_counter  = 32;
        code_count       = 0;
        code_reset_count = 0;
        c_buffer_idx       = 0;

        // leave space for the 4 flags
        fwrite(&code_count, sizeof(int), 4, cFile);

        // init code buffer
        AllocBufferC(MAX_BUFFER_LEN);
        c_buffer[0] = 0;
    }

    // generate reverse code for the data
    code_reverse = GenerateReverseCode(data);

    // put the data in the tree
    BuildDHT(data);

    // check for overflow and reset code counter
    if(code_count + 1 > MAX_FREQ)
    {
        code_count = DHTroot.freq;
        ++code_reset_count;
    }
    else ++code_count;

    // convert the reversed code to original code
    for(i = 0; i < code_length; i++)
    {
        code <<= 1;
        code |= code_reverse & 1;
        code_reverse >>= 1;
    }

    // calculate how many bits would remain in current buffer element after putting the code
    dcs.bit_counter -= code_length;

    // if enough bits left to put the code, just put the code
    if(dcs.bit_counter > 0)
    {
        code <<= dcs.bit_counter;
        c_buffer[c_buffer_idx] |= code;
    }
    // if it will fit in perfectly, put the code, and increment buffer index
    else if(dcs.bit_counter == 0)
    {
        c_buffer[c_buffer_idx] |= code;
        dcs.bit_counter = 32;

        // prevent buffer overflow
        if(++c_buffer_idx == c_buffer_size) GrowBufferC();

        // get next buffer element ready
        c_buffer[c_buffer_idx] = 0;
    }
    // if not enough bits left to put the code
    else
    {
        // retrieve part of the code
        for(i = 0; i > dcs.bit_counter; i--)
        {
            code_temp <<= 1;
            code_temp |= code & 1;
            code >>= 1;
        }
        // put part of the code in the remaining bits of the current buffer element
        c_buffer[c_buffer_idx] |= code;

        // retrieve rest of the code
        for(i = 0; i > dcs.bit_counter; i--)
        {
            code <<= 1;
            code |= code_temp & 1;
            code_temp >>= 1;
        }
        dcs.bit_counter += 32;
        code <<= dcs.bit_counter;
        // prevent buffer overflow
        if(++c_buffer_idx == c_buffer_size) GrowBufferC();

        // put the rest of the code in the next buffer element
        c_buffer[c_buffer_idx] = code;
    }
}

// decode and return the next data from c_buffer
unsigned char DecodeBuffer()
{
    struct DHTNode *node_ptr = &DHTroot; // start with the root node
    unsigned char data        = 0; // decoded data
    int isData = 0;
    int i;

    // if it's the first code, reset everything and decode the first data
    // otherwise, get the next data
    if(!DHTroot.freq)
    {
        c_buffer_idx  = 0;
        end_of_buffer = 0;

        dcs.code_slice = c_buffer[c_buffer_idx];
        data = (unsigned char)(dcs.code_slice >> 24);
        dcs.code_slice <<= 8;

        dcs.nCodeReset    = 0;
        dcs.nCode         = 0;
        dcs.bit_counter   = 8;
    }
    else
    {
        do
        {
            isData = 0;

            // if it's the end of the code slice, get the next slice
            if(dcs.bit_counter == 32)
            {

                dcs.code_slice = c_buffer[++c_buffer_idx];
                dcs.bit_counter = 0;
            }

            // if next bit is 1, go to right. if it is 0, goto left
            if(dcs.code_slice & 0x80000000)
                node_ptr = node_ptr->right;
            else
                node_ptr = node_ptr->left;
            dcs.code_slice <<= 1;
            ++dcs.bit_counter;

            // if it is a data node, just copy the data from that node
            if(node_ptr && !node_ptr->right)
            {
                data = node_ptr->value;
                isData = 1;
            }

            // if the it's a new data, get the next 8 bits
            else if(node_ptr == NULL)
            {
                for(i = 0; i < 8; i++)
                {
                    // if it's the end of the code slice, get the next slice.
                    if(dcs.bit_counter == 32)
                    {

                        dcs.code_slice = c_buffer[++c_buffer_idx];
                        dcs.bit_counter = 0;
                    }
                    data <<= 1;
                    data |= dcs.code_slice >> 31;
                    dcs.code_slice <<= 1;
                    ++dcs.bit_counter;
                }
                isData = 1;
            } // end of 'else if(node_ptr==NULL)'
        }
        while (!isData);
    } // end of 'if(DHTroot.freq)'

    BuildDHT(data);

    // prevent code count overflow
    if(dcs.nCode + 1 > MAX_FREQ)
    {
        dcs.nCode = DHTroot.freq;
        ++dcs.nCodeReset;
    }
    else ++dcs.nCode;

    // if everything has been decoded, set end_of_buffer flag
    if(dcs.nCodeReset == code_reset_count && dcs.nCode == code_count)
    {
        end_of_buffer = 1;
    }

    return data;  // return the decoded data
}

static void AllocBufferC(int size)
{
    c_buffer_size = size;
    c_buffer = (UINT32 *)realloc(c_buffer, c_buffer_size * 4);
}

// prevent c_buffer overflow while encoding
static void GrowBufferC()
{
    // flush to disk periodically
    fwrite(c_buffer + c_buffer_size - MAX_BUFFER_LEN, 4, MAX_BUFFER_LEN, cFile);
    AllocBufferC(c_buffer_size + MAX_BUFFER_LEN);
}

// prevent d_buffer foverflow while encoding
static void ReloadBufferD()
{
    fread(d_buffer, 4, MAX_BUFFER_LEN, dFile);
    d_buffer_idx = 0;
}

// prevent d_buffer overflow while decoding
static void ResetBufferD()
{
    fwrite(d_buffer, 4, MAX_BUFFER_LEN, dFile);
    d_buffer_idx = 0;
}

//#
//#             Functions for File I/O
//#
//##############################################################################

// return 0 if the compressed file is opened sucessfully, 1 otherwise
int OpenCompressedFile(char *file_name, char *mode)
{
    if(cFile) fclose(cFile);
    cFile = NULL;

    cFile = fopen(file_name, mode);
    if (cFile) return 0;

    return 1;
}

// Always returns 0
int EmbedCompressedFile(FILE *pEmb, int nOffset)
{
    if(cFile) fclose(cFile);
    cFile = NULL;

    cFile = pEmb;
    bEmbed = 1;
    if (nOffset >= 0)
    {
        embed_offset = nOffset;
        fseek(cFile, nOffset, SEEK_SET);
    }
    else
    {
        if (nOffset == -2)
        {
            fseek(cFile, 0, SEEK_END);
        }
        embed_offset = ftell(cFile);
    }
    return 0;
}

// return 0 if the decompressed file is opened sucessfully, 1 otherwise
int OpenDecompressedFile(char *file_name, char *mode)
{
    dFile = NULL;
    dFile = fopen(file_name, mode);
    if (dFile) return 0;
    return 1;
}

// load the compressed file into the c_buffer
// - call this function only if the compressed file is opened successfully
void LoadCompressedFile()
{
    int byte_count;
    int buffer_reset_count;

    // load the flags
    fread(&byte_count, sizeof(int), 1, cFile);
    fread(&code_count, sizeof(int), 1, cFile);
    fread(&code_reset_count, sizeof(int), 1, cFile);
    fread(&buffer_reset_count, sizeof(int), 1, cFile);

    // load everything into the buffer
    AllocBufferC((buffer_reset_count + 1)*MAX_BUFFER_LEN);
    fread(c_buffer, 1, byte_count - 16, cFile);		// note:  byte_count includes the size of the headers
}

// this method is used when unfreezing the compression status
// it flushes the contents of the compressed file to disk
static void DoWriteCompressedFile()
{
    // save file size, code count, etc
    SaveResult();

    // handle file embedding
    fseek(cFile, embed_offset, SEEK_SET);

    fwrite(&nCompressedFileSize, sizeof(int), 1, cFile);
    fwrite(&nCodeCount, sizeof(int), 1, cFile);
    fwrite(&nCodeResetCount, sizeof(int), 1, cFile);
    fwrite(&nBufferResetCount, sizeof(int), 1, cFile);

    // flush entire contents of compress buffer
    fwrite(c_buffer, 4, c_buffer_idx + 1, cFile);
}

// write whatever is left in the c_buffer to the
// compressed file, and close the compressed file
// - use this if the compressed file was opened in 'write' mode
void WriteCompressedFile()
{
    if(cFile)
    {
        DoWriteCompressedFile();
        CloseCompressedFile();
    }
}

// write whatever is left in the d_buffer to the
// decompressed file, and close the decompressed file
// - use this if the decompressed file was opened in 'write' mode
void WriteDecompressedFile(int bytes_remain)
{
    UINT32 code_slice;
    int i;

    if(dFile)
    {
        // write the buffer to the file
        if(d_buffer_idx) fwrite(d_buffer, 4, d_buffer_idx, dFile);
        if(bytes_remain)
        {
            code_slice = d_buffer[d_buffer_idx];
            for(i = 0; i < (4 - bytes_remain); i++)
            {
                code_slice >>= 8;
            }
            fwrite(&code_slice, 1, bytes_remain, dFile);
        }

        fclose(dFile);
        dFile = NULL;
    }
}

// close the compressed file
// - use this if the compressed file was opened in 'read' mode
void CloseCompressedFile()
{
    if(cFile)
    {
        // handle file embedding
        if (!bEmbed)
        {
            fclose(cFile);
        }

        cFile = NULL;
        embed_offset = 0;
        bEmbed = 0;

#ifdef _DEBUG
        // PrintTree();
        CheckList();
#endif

        DestroyDHT();

        free(c_buffer);
        c_buffer = NULL;
        c_buffer_size = 0;
    }
}

// close the decompressed file
// - use this if the decompressed file was opened in 'read' mode
void CloseDecompressedFile()
{
    if(dFile)
    {
        fclose(dFile);
        dFile = NULL;
    }
}

//#
//#             Utility Functions for Debugging Purpose
//#
//##############################################################################

// print the node frequency while reverse level traversing
void PrintFreqTraverse()
{
    int curr_idx = list_idx;

    printf("Frequency Traverse -");
    while(node_list[curr_idx])
    {
        printf(" %d", node_list[curr_idx]->freq);
        if(node_list[curr_idx]->value) printf(":%c", node_list[curr_idx]->value);
        ++curr_idx;
    }
}

// print the tree view (rotated -90 degrees)
void PrintTreeBreath(struct DHTNode *node_ptr, int spaces)
{
    int i;
    int num_digits;
    int tab_len;
    if(node_ptr)
    {
        num_digits = node_ptr->freq;
        tab_len = spaces;
        PrintTreeBreath(node_ptr->right, spaces + 7); // right tree first

        num_digits = num_digits / 10;
        while(num_digits)
        {
            --tab_len;
            num_digits = num_digits / 10;
        }
        for(i = 0; i < tab_len; i++) printf(" ");
        printf("%d", node_ptr->freq);
        if(node_ptr->value) printf(":%c", node_ptr->value);
        printf("\n");

        PrintTreeBreath(node_ptr->left, spaces + 7); // then left tree
    }
}

// print the header, then print the tree in breath order
void PrintTree()
{
    printf("View of the Tree (rotated -90 degrees)\n");
    PrintTreeBreath(&DHTroot, 0);
}

// check the reverse traverse list and print any frequencies that are out of order
#ifdef _DEBUG
static void CheckList()
{
    int curr_idx = list_idx;
    int count_errors = 0;
    while(curr_idx < MAX_LIST_LEN - 3)
    {
        if(node_list[curr_idx]->freq > node_list[curr_idx + 1]->freq)
            printf("\nError: list is out of order.\n%d\n%d\n", node_list[curr_idx]->freq, node_list[curr_idx + 1]->freq);

        curr_idx++;
        count_errors++;
    }
    if(!count_errors)
        printf("\nNo errors in reverse traverse list.\n");
}
#endif

// dump the buffer to the screen
void PrintBuffer()
{
    UINT32 i, j;
    j = (UINT32)c_buffer_idx;

    printf("buffer = ");
    for(i = 0; i <= j; i++) printf("%.8X ", c_buffer[i]);
}

// save compression result
static void SaveResult()
{
    nCompressedFileSize = 16 + (c_buffer_idx + 1) * 4; // convert to Bytes
    nCodeCount = code_count;
    nCodeResetCount = code_reset_count;
    nBufferIdx = c_buffer_idx;
    // nBufferResetCount is retained for backwards compatability
    nBufferResetCount = c_buffer_idx / MAX_BUFFER_LEN;
}

// print file size, how many codes, etc
void PrintResult()
{
    printf("\ncompressed file size = %.3f KB\n\n", (double)nCompressedFileSize / 1024.0); // convert to KB
    printf("      max code count = %u\n", MAX_FREQ);
    printf("  current code count = %u\n", nCodeCount);
    printf("  # code count reset = %d\n\n", nCodeResetCount);
    printf("    max buffer size  = %.3f KB\n", (float)(4 * MAX_BUFFER_LEN) / 1024.0);
    printf("    max buffer index = %d\n", MAX_BUFFER_LEN);
    printf("current buffer index = %u\n", nBufferIdx);
    printf("    # buffer re-used = %d\n\n", nBufferResetCount);
}

//#
//#             Compression Status Freezing
//#
//##############################################################################

static inline void Write32(unsigned char *&ptr, const unsigned long v)
{
    *ptr++ = (unsigned char)(v & 0xff);
    *ptr++ = (unsigned char)((v >> 8) & 0xff);
    *ptr++ = (unsigned char)((v >> 16) & 0xff);
    *ptr++ = (unsigned char)((v >> 24) & 0xff);
}

static inline unsigned long Read32(const unsigned char *&ptr)
{
    unsigned long v;
    v = (unsigned long)(*ptr++);
    v |= (unsigned long)((*ptr++) << 8);
    v |= (unsigned long)((*ptr++) << 16);
    v |= (unsigned long)((*ptr++) << 24);
    return v;
}

static inline void Write16(unsigned char *&ptr, const unsigned short v)
{
    *ptr++ = (unsigned char)(v & 0xff);
    *ptr++ = (unsigned char)((v >> 8) & 0xff);
}

static inline unsigned short Read16(const unsigned char *&ptr)
{
    unsigned short v;
    v = (unsigned short)(*ptr++);
    v |= (unsigned short)((*ptr++) << 8);
    return v;
}

/*
struct DHTFreezeStruct
{
	struct DHTFreezeStatus header;
	struct DHTFreezeNode
	{
		unsigned int freq;
		unsigned char val;
		short left, right, parent
	} node_list[n_nodes]
}
*/

struct DHTFreezeStatus
{
    int           n_nodes;
    unsigned long null_node_p;
    int           bit_counter;
    unsigned int  code_count;
    int           code_reset_count;
    int           c_buffer_idx;
};

static const int DHTFreezeStatusSize = 6 * 4;
static const int DHTNodeSize = 12;

static inline int IndexForNode(const DHTNode *node)
{
    if(!node)			return 0xffff;
    return				node->l_index;
}

static inline DHTNode *NodeForIndex(int idx)
{
    switch(idx)
    {
    case 0xffff:
        return NULL;
    default:
        return node_list[idx];
    }
}

static void WriteNode(unsigned char *&ptr, const DHTNode *node)
{
    Write32(ptr, node->freq);
    Write16(ptr, node->value);
    Write16(ptr, IndexForNode(node->left));
    Write16(ptr, IndexForNode(node->right));
    Write16(ptr, IndexForNode(node->parent));
}

static void ReadNode(const unsigned char *&ptr, DHTNode *node)
{
    node->freq = Read32(ptr);
    node->value = Read16(ptr);
    node->left = NodeForIndex(Read16(ptr));
    node->right = NodeForIndex(Read16(ptr));
    node->parent = NodeForIndex(Read16(ptr));
}

static void FreezeDHT(const struct DHTFreezeStatus &status, unsigned char *&ptr)
{
    Write32(ptr, status.n_nodes);
    Write32(ptr, status.null_node_p);
    Write32(ptr, status.bit_counter);
    Write32(ptr, status.code_count);
    Write32(ptr, status.code_reset_count);
    Write32(ptr, status.c_buffer_idx);

    int n_nodes = status.n_nodes;
    while(n_nodes)
    {
        WriteNode(ptr, node_list[MAX_LIST_LEN - 1 - n_nodes]);
        --n_nodes;
    }
}

static int UnfreezeDHT(struct DHTFreezeStatus *status, const unsigned char *&ptr, const int buf_size)
{
    if(buf_size < DHTFreezeStatusSize)
    {
        return 1;
    }

    status->n_nodes            = Read32(ptr);
    status->null_node_p        = Read32(ptr);
    status->bit_counter        = Read32(ptr);
    status->code_count         = Read32(ptr);
    status->code_reset_count   = Read32(ptr);
    status->c_buffer_idx       = Read32(ptr);

    if(buf_size < (DHTFreezeStatusSize + status->n_nodes * DHTNodeSize))
    {
        return 1;
    }

    DestroyDHT();

    int n = status->n_nodes;
    if(n)
    {
        node_list[--list_idx] = &DHTroot;
        --n;
    }
    while(n)
    {
        node_list[--list_idx] = (struct DHTNode *)malloc(sizeof(struct DHTNode));
        --n;
    }

    n = status->n_nodes;
    while(n)
    {
        int idx = MAX_LIST_LEN - 1 - n;
        ReadNode(ptr, node_list[idx]);
        node_list[idx]->l_index = idx;
        if(!node_list[idx]->right)
        {
            look_up_table[node_list[idx]->value] = node_list[idx];
        }
        --n;
    }

    null_node_ptr = (status->null_node_p == 0xffffffff) ? &DHTroot : node_list[status->null_node_p];

    return 0;
}

int FreezeDecode(unsigned char **buf, int *size)
{
    // compute the size required for the buffer
    int n_nodes = MAX_LIST_LEN - 1 - list_idx;
    int dht_size = DHTFreezeStatusSize + n_nodes * DHTNodeSize;
    int buf_size = 4 + dht_size + (c_buffer_idx + 1) * 4;

    *buf = (unsigned char *)malloc(buf_size);
    *size = buf_size;

    if(!(*buf))
    {
        return 1;
    }

    DHTFreezeStatus status;
    status.n_nodes            = n_nodes;
    status.null_node_p        = (null_node_ptr == &DHTroot) ? 0xffffffff : null_node_ptr->l_index;
    status.bit_counter        = dcs.bit_counter;
    status.code_count         = dcs.nCode;
    status.code_reset_count   = dcs.nCodeReset;
    status.c_buffer_idx       = c_buffer_idx;

    unsigned char *ptr = *buf;
    Write32(ptr, dht_size);							// write DHT status size
    FreezeDHT(status, ptr);							// write DHT status
    memcpy(ptr, c_buffer, (c_buffer_idx + 1) * 4);		// write code buffer

    return 0;
}

int UnfreezeDecode(const unsigned char *buf, int size)
{
    if(size < 4)
    {
        return 1;
    }

    const unsigned char *ptr = buf;
    int dht_size = (int)Read32(ptr);				// read DHT status size

    DHTFreezeStatus status;
    if(UnfreezeDHT(&status, ptr, dht_size))			// read DHT status
    {
        return 1;
    }

    // NOTE:
    // UnfreezeDecode is a special case.  In order to
    // implement "rewind" functionality, it's necessary
    // to restore the state of the decode, but leave
    // the contents of the code buffer intact

#if 0
    // restore code buffer
    int n_buffers   = status.c_buffer_idx / MAX_BUFFER_LEN;
    AllocBufferC((n_buffers + 1)*MAX_BUFFER_LEN);
    memcpy(c_buffer, ptr, (status.c_buffer_idx + 1) * 4);	// read code buffer
#endif

    // Here we make a weak check against attempting to
    // seek past the end of the code buffer
    if(status.c_buffer_idx >= c_buffer_size)
    {
        return 1;
    }

    dcs.bit_counter = status.bit_counter;
    dcs.nCode       = status.code_count;
    dcs.nCodeReset  = status.code_reset_count;

    c_buffer_idx    = status.c_buffer_idx;
    dcs.code_slice  = c_buffer[c_buffer_idx] << dcs.bit_counter;

    return 0;
}

int FreezeEncode(unsigned char **buf, int *size)
{
    // compute the size required for the buffer
    int n_nodes = MAX_LIST_LEN - 1 - list_idx;
    int dht_size = DHTFreezeStatusSize + n_nodes * DHTNodeSize;
    int buf_size = 4 + dht_size + (c_buffer_idx + 1) * 4;

    *buf = (unsigned char *)malloc(buf_size);
    *size = buf_size;

    if(!(*buf))
    {
        return 1;
    }

    DHTFreezeStatus status;
    status.n_nodes            = n_nodes;
    status.null_node_p        = (null_node_ptr == &DHTroot) ? 0xffffffff : null_node_ptr->l_index;
    status.bit_counter        = 32 - dcs.bit_counter;  // while encoding, bit_counter equals bits remaining in slice
    status.code_count         = code_count;
    status.code_reset_count   = code_reset_count;
    status.c_buffer_idx       = c_buffer_idx;

    unsigned char *ptr = *buf;
    Write32(ptr, dht_size);							// write DHT status size
    FreezeDHT(status, ptr);							// write DHT status
    memcpy(ptr, c_buffer, (c_buffer_idx + 1) * 4);		// write code buffer

    return 0;
}

int UnfreezeEncode(const unsigned char *buf, int size)
{
    if(size < 4)
    {
        return 1;
    }

    const unsigned char *ptr = buf;
    int dht_size = (int)Read32(ptr);				// read DHT status size

    DHTFreezeStatus status;
    if(UnfreezeDHT(&status, ptr, dht_size))			// read DHT status
    {
        return 1;
    }

    int buf_size = 4 + dht_size + (status.c_buffer_idx + 1) * 4;
    if(buf_size > size)
    {
        return 1;
    }

    dcs.bit_counter    = 32 - status.bit_counter;   // while encoding, bit_counter equals bits remaining in slice
    code_count         = status.code_count;
    code_reset_count   = status.code_reset_count;
    c_buffer_idx       = status.c_buffer_idx;

    int n_buffers = status.c_buffer_idx / MAX_BUFFER_LEN;
    AllocBufferC((n_buffers + 1)*MAX_BUFFER_LEN);
    memcpy(c_buffer, ptr, (status.c_buffer_idx + 1) * 4);	// read code buffer
    DoWriteCompressedFile();							// flush to disk
    fseek(cFile, embed_offset + 16 + (n_buffers * MAX_BUFFER_LEN) * 4, SEEK_SET);		// position write ptr for periodic flush

    // mask off the unread bits from the current code
    // this should be unneccessary, but it doesn't hurt
    c_buffer[c_buffer_idx] &= (0xffffffff << dcs.bit_counter);

    return 0;
}
